package chapter7.graph;

/**
 * Created by lili on 2017/7/1.
 */
//【例7.3】  构造带权无向图G8的最小生成树。

public class WeightedUndiG8                              //带权无向图G8
{
    public static void main(String args[])
    {
        String[] vertices={"A","B","C","D","E","F","G","H"};
        Edge edges[]={new Edge(0,1,12), new Edge(0,2,31),
                new Edge(1,0,12), new Edge(1,3,23),
                new Edge(2,0,31), new Edge(2,3,15),
                new Edge(3,1,23), new Edge(3,2,15), new Edge(3,4,11), new Edge(3,5,4),
                new Edge(4,3,11), new Edge(4,5,5), new Edge(4,6,27),
                new Edge(5,3,4), new Edge(5,4,5), new Edge(5,6,63), new Edge(5,7,17),
                new Edge(6,4,27), new Edge(6,5,63), new Edge(6,7,18),
                new Edge(7,5,17), new Edge(7,6,18)};
        AdjMatrixGraph<String> graph = new AdjMatrixGraph<String>(vertices, edges);
        System.out.println("带权无向图G8，"+graph.toString());
        graph.minSpanTree_prim();                          //构造带权图最小生成树的普里姆算法
        for (int i=0; i<graph.vertexCount(); i++)
            graph.shortestPath(i);               //顶点vi的单源最短路径，Dijkstra算法

    }
}
/*
程序运行结果如下：
带权无向图G8，顶点集合：(A, B, C, D, E, F, G, H)
邻接矩阵:
  0  12  31  ∞  ∞  ∞  ∞  ∞
  12  0  ∞  23  ∞  ∞  ∞  ∞
  31  ∞  0  15  ∞  ∞  ∞  ∞
  ∞  23  15  0  11  4  ∞  ∞
  ∞  ∞  ∞  11  0  5  27  ∞
  ∞  ∞  ∞  4  5  0  63  17
  ∞  ∞  ∞  ∞  27  63  0  18
  ∞  ∞  ∞  ∞  ∞  17  18  0

mst数组初值：(0,1,12)(0,2,31)(0,3,99999)(0,4,99999)(0,5,99999)(0,6,99999)(0,7,99999)
mst数组：(0,1,12)(0,2,31)(1,3,23)(0,4,99999)(0,5,99999)(0,6,99999)(0,7,99999)
mst数组：(0,1,12)(1,3,23)(3,2,15)(3,4,11)(3,5,4)(0,6,99999)(0,7,99999)
mst数组：(0,1,12)(1,3,23)(3,5,4)(5,4,5)(3,2,15)(5,6,63)(5,7,17)
mst数组：(0,1,12)(1,3,23)(3,5,4)(5,4,5)(3,2,15)(4,6,27)(5,7,17)
mst数组：(0,1,12)(1,3,23)(3,5,4)(5,4,5)(3,2,15)(4,6,27)(5,7,17)
mst数组：(0,1,12)(1,3,23)(3,5,4)(5,4,5)(3,2,15)(5,7,17)(7,6,18)
mst数组：(0,1,12)(1,3,23)(3,5,4)(5,4,5)(3,2,15)(5,7,17)(7,6,18)
最小生成树的边集合：(0,1,12) (1,3,23) (3,5,4) (5,4,5) (3,2,15) (5,7,17) (7,6,18) ，最小代价为94

vset数组{1,0,0,0,0,0,0,0}	path数组{-1,0,0,-1,-1,-1,-1,-1}	dist数组{0,12,31,99999,99999,99999,99999,99999}
vset数组{1,1,0,0,0,0,0,0}	path数组{-1,0,0,1,-1,-1,-1,-1}	dist数组{0,12,31,35,99999,99999,99999,99999}
vset数组{1,1,1,0,0,0,0,0}	path数组{-1,0,0,1,-1,-1,-1,-1}	dist数组{0,12,31,35,99999,99999,99999,99999}
vset数组{1,1,1,1,0,0,0,0}	path数组{-1,0,0,1,3,3,-1,-1}	dist数组{0,12,31,35,46,39,99999,99999}
vset数组{1,1,1,1,0,1,0,0}	path数组{-1,0,0,1,5,3,5,5}	dist数组{0,12,31,35,44,39,102,56}
vset数组{1,1,1,1,1,1,0,0}	path数组{-1,0,0,1,5,3,4,5}	dist数组{0,12,31,35,44,39,71,56}
vset数组{1,1,1,1,1,1,0,1}	path数组{-1,0,0,1,5,3,4,5}	dist数组{0,12,31,35,44,39,71,56}
vset数组{1,1,1,1,1,1,1,1}	path数组{-1,0,0,1,5,3,4,5}	dist数组{0,12,31,35,44,39,71,56}
从顶点A到其他顶点的最短路径如下：
(A,B)长度为12
(A,C)长度为31
(A,B,D)长度为35
(A,B,D,F,E)长度为44
(A,B,D,F)长度为39
(A,B,D,F,E,G)长度为71
(A,B,D,F,H)长度为56

vset数组{0,1,0,0,0,0,0,0}	path数组{1,-1,-1,1,-1,-1,-1,-1}	dist数组{12,0,99999,23,99999,99999,99999,99999}
vset数组{1,1,0,0,0,0,0,0}	path数组{1,-1,0,1,-1,-1,-1,-1}	dist数组{12,0,43,23,99999,99999,99999,99999}
vset数组{1,1,0,1,0,0,0,0}	path数组{1,-1,3,1,3,3,-1,-1}	dist数组{12,0,38,23,34,27,99999,99999}
vset数组{1,1,0,1,0,1,0,0}	path数组{1,-1,3,1,5,3,5,5}	dist数组{12,0,38,23,32,27,90,44}
vset数组{1,1,0,1,1,1,0,0}	path数组{1,-1,3,1,5,3,4,5}	dist数组{12,0,38,23,32,27,59,44}
vset数组{1,1,1,1,1,1,0,0}	path数组{1,-1,3,1,5,3,4,5}	dist数组{12,0,38,23,32,27,59,44}
vset数组{1,1,1,1,1,1,0,1}	path数组{1,-1,3,1,5,3,4,5}	dist数组{12,0,38,23,32,27,59,44}
vset数组{1,1,1,1,1,1,1,1}	path数组{1,-1,3,1,5,3,4,5}	dist数组{12,0,38,23,32,27,59,44}
从顶点B到其他顶点的最短路径如下：
(B,A)长度为12
(B,D,C)长度为38
(B,D)长度为23
(B,D,F,E)长度为32
(B,D,F)长度为27
(B,D,F,E,G)长度为59
(B,D,F,H)长度为44

vset数组{0,0,1,0,0,0,0,0}	path数组{2,-1,-1,2,-1,-1,-1,-1}	dist数组{31,99999,0,15,99999,99999,99999,99999}
vset数组{0,0,1,1,0,0,0,0}	path数组{2,3,-1,2,3,3,-1,-1}	dist数组{31,38,0,15,26,19,99999,99999}
vset数组{0,0,1,1,0,1,0,0}	path数组{2,3,-1,2,5,3,5,5}	dist数组{31,38,0,15,24,19,82,36}
vset数组{0,0,1,1,1,1,0,0}	path数组{2,3,-1,2,5,3,4,5}	dist数组{31,38,0,15,24,19,51,36}
vset数组{1,0,1,1,1,1,0,0}	path数组{2,3,-1,2,5,3,4,5}	dist数组{31,38,0,15,24,19,51,36}
vset数组{1,0,1,1,1,1,0,1}	path数组{2,3,-1,2,5,3,4,5}	dist数组{31,38,0,15,24,19,51,36}
vset数组{1,1,1,1,1,1,0,1}	path数组{2,3,-1,2,5,3,4,5}	dist数组{31,38,0,15,24,19,51,36}
vset数组{1,1,1,1,1,1,1,1}	path数组{2,3,-1,2,5,3,4,5}	dist数组{31,38,0,15,24,19,51,36}
从顶点C到其他顶点的最短路径如下：
(C,A)长度为31
(C,D,B)长度为38
(C,D)长度为15
(C,D,F,E)长度为24
(C,D,F)长度为19
(C,D,F,E,G)长度为51
(C,D,F,H)长度为36

vset数组{0,0,0,1,0,0,0,0}	path数组{-1,3,3,-1,3,3,-1,-1}	dist数组{99999,23,15,0,11,4,99999,99999}
vset数组{0,0,0,1,0,1,0,0}	path数组{-1,3,3,-1,5,3,5,5}	dist数组{99999,23,15,0,9,4,67,21}
vset数组{0,0,0,1,1,1,0,0}	path数组{-1,3,3,-1,5,3,4,5}	dist数组{99999,23,15,0,9,4,36,21}
vset数组{0,0,1,1,1,1,0,0}	path数组{2,3,3,-1,5,3,4,5}	dist数组{46,23,15,0,9,4,36,21}
vset数组{0,0,1,1,1,1,0,1}	path数组{2,3,3,-1,5,3,4,5}	dist数组{46,23,15,0,9,4,36,21}
vset数组{0,1,1,1,1,1,0,1}	path数组{1,3,3,-1,5,3,4,5}	dist数组{35,23,15,0,9,4,36,21}
vset数组{1,1,1,1,1,1,0,1}	path数组{1,3,3,-1,5,3,4,5}	dist数组{35,23,15,0,9,4,36,21}
vset数组{1,1,1,1,1,1,1,1}	path数组{1,3,3,-1,5,3,4,5}	dist数组{35,23,15,0,9,4,36,21}
从顶点D到其他顶点的最短路径如下：
(D,B,A)长度为35
(D,B)长度为23
(D,C)长度为15
(D,F,E)长度为9
(D,F)长度为4
(D,F,E,G)长度为36
(D,F,H)长度为21

vset数组{0,0,0,0,1,0,0,0}	path数组{-1,-1,-1,4,-1,4,4,-1}	dist数组{99999,99999,99999,11,0,5,27,99999}
vset数组{0,0,0,0,1,1,0,0}	path数组{-1,-1,-1,5,-1,4,4,5}	dist数组{99999,99999,99999,9,0,5,27,22}
vset数组{0,0,0,1,1,1,0,0}	path数组{-1,3,3,5,-1,4,4,5}	dist数组{99999,32,24,9,0,5,27,22}
vset数组{0,0,0,1,1,1,0,1}	path数组{-1,3,3,5,-1,4,4,5}	dist数组{99999,32,24,9,0,5,27,22}
vset数组{0,0,1,1,1,1,0,1}	path数组{2,3,3,5,-1,4,4,5}	dist数组{55,32,24,9,0,5,27,22}
vset数组{0,0,1,1,1,1,1,1}	path数组{2,3,3,5,-1,4,4,5}	dist数组{55,32,24,9,0,5,27,22}
vset数组{0,1,1,1,1,1,1,1}	path数组{1,3,3,5,-1,4,4,5}	dist数组{44,32,24,9,0,5,27,22}
vset数组{1,1,1,1,1,1,1,1}	path数组{1,3,3,5,-1,4,4,5}	dist数组{44,32,24,9,0,5,27,22}
从顶点E到其他顶点的最短路径如下：
(E,F,D,B,A)长度为44
(E,F,D,B)长度为32
(E,F,D,C)长度为24
(E,F,D)长度为9
(E,F)长度为5
(E,G)长度为27
(E,F,H)长度为22

vset数组{0,0,0,0,0,1,0,0}	path数组{-1,-1,-1,5,5,-1,5,5}	dist数组{99999,99999,99999,4,5,0,63,17}
vset数组{0,0,0,1,0,1,0,0}	path数组{-1,3,3,5,5,-1,5,5}	dist数组{99999,27,19,4,5,0,63,17}
vset数组{0,0,0,1,1,1,0,0}	path数组{-1,3,3,5,5,-1,4,5}	dist数组{99999,27,19,4,5,0,32,17}
vset数组{0,0,0,1,1,1,0,1}	path数组{-1,3,3,5,5,-1,4,5}	dist数组{99999,27,19,4,5,0,32,17}
vset数组{0,0,1,1,1,1,0,1}	path数组{2,3,3,5,5,-1,4,5}	dist数组{50,27,19,4,5,0,32,17}
vset数组{0,1,1,1,1,1,0,1}	path数组{1,3,3,5,5,-1,4,5}	dist数组{39,27,19,4,5,0,32,17}
vset数组{0,1,1,1,1,1,1,1}	path数组{1,3,3,5,5,-1,4,5}	dist数组{39,27,19,4,5,0,32,17}
vset数组{1,1,1,1,1,1,1,1}	path数组{1,3,3,5,5,-1,4,5}	dist数组{39,27,19,4,5,0,32,17}
从顶点F到其他顶点的最短路径如下：
(F,D,B,A)长度为39
(F,D,B)长度为27
(F,D,C)长度为19
(F,D)长度为4
(F,E)长度为5
(F,E,G)长度为32
(F,H)长度为17

vset数组{0,0,0,0,0,0,1,0}	path数组{-1,-1,-1,-1,6,6,-1,6}	dist数组{99999,99999,99999,99999,27,63,0,18}
vset数组{0,0,0,0,0,0,1,1}	path数组{-1,-1,-1,-1,6,7,-1,6}	dist数组{99999,99999,99999,99999,27,35,0,18}
vset数组{0,0,0,0,1,0,1,1}	path数组{-1,-1,-1,4,6,4,-1,6}	dist数组{99999,99999,99999,38,27,32,0,18}
vset数组{0,0,0,0,1,1,1,1}	path数组{-1,-1,-1,5,6,4,-1,6}	dist数组{99999,99999,99999,36,27,32,0,18}
vset数组{0,0,0,1,1,1,1,1}	path数组{-1,3,3,5,6,4,-1,6}	dist数组{99999,59,51,36,27,32,0,18}
vset数组{0,0,1,1,1,1,1,1}	path数组{2,3,3,5,6,4,-1,6}	dist数组{82,59,51,36,27,32,0,18}
vset数组{0,1,1,1,1,1,1,1}	path数组{1,3,3,5,6,4,-1,6}	dist数组{71,59,51,36,27,32,0,18}
vset数组{1,1,1,1,1,1,1,1}	path数组{1,3,3,5,6,4,-1,6}	dist数组{71,59,51,36,27,32,0,18}
从顶点G到其他顶点的最短路径如下：
(G,E,F,D,B,A)长度为71
(G,E,F,D,B)长度为59
(G,E,F,D,C)长度为51
(G,E,F,D)长度为36
(G,E)长度为27
(G,E,F)长度为32
(G,H)长度为18

vset数组{0,0,0,0,0,0,0,1}	path数组{-1,-1,-1,-1,-1,7,7,-1}	dist数组{99999,99999,99999,99999,99999,17,18,0}
vset数组{0,0,0,0,0,1,0,1}	path数组{-1,-1,-1,5,5,7,7,-1}	dist数组{99999,99999,99999,21,22,17,18,0}
vset数组{0,0,0,0,0,1,1,1}	path数组{-1,-1,-1,5,5,7,7,-1}	dist数组{99999,99999,99999,21,22,17,18,0}
vset数组{0,0,0,1,0,1,1,1}	path数组{-1,3,3,5,5,7,7,-1}	dist数组{99999,44,36,21,22,17,18,0}
vset数组{0,0,0,1,1,1,1,1}	path数组{-1,3,3,5,5,7,7,-1}	dist数组{99999,44,36,21,22,17,18,0}
vset数组{0,0,1,1,1,1,1,1}	path数组{2,3,3,5,5,7,7,-1}	dist数组{67,44,36,21,22,17,18,0}
vset数组{0,1,1,1,1,1,1,1}	path数组{1,3,3,5,5,7,7,-1}	dist数组{56,44,36,21,22,17,18,0}
vset数组{1,1,1,1,1,1,1,1}	path数组{1,3,3,5,5,7,7,-1}	dist数组{56,44,36,21,22,17,18,0}
从顶点H到其他顶点的最短路径如下：
(H,F,D,B,A)长度为56
(H,F,D,B)长度为44
(H,F,D,C)长度为36
(H,F,D)长度为21
(H,F,E)长度为22
(H,F)长度为17
(H,G)长度为18


*/

